package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * leetcode 46. 全排列
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/14 11:29
 */
public class E46 {
    /*
         1                   2                  3                   4
      /  |  \             /  |  \            /  |  \             /  |  \
     2   3   4          1   3   4          1   2   4           1   2   3
    /\  /\   /\        /\  /\   /\        /\  /\   /\         /\  /\   /\
   3 4 2 4  2 3       3 4 1 4  1 3       2 4 1 4  1 2        2 3 1 3  1 2
   | | | |  | |       | | | |  | |       | | | |  | |        | | | |  | |
   4 3 4 2  3 2       4 3 4 1  3 1       4 2 4 1  2 1        3 2 3 1  2 1

     P(4,4) = 24 正确的
     */

    /**
     * 全排列
     * @param nums nums
     * @return result
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(nums, result, new LinkedList<>(), new boolean[nums.length]);
        return result;
    }

    /**
     * 回溯，实质就是对每棵树进行一次深度优先遍历
     * @param nums nums
     * @param result 结果
     * @param currentPath 当前路径 栈
     * @param visited 访问标记
     */
    private void dfs(int[] nums, List<List<Integer>> result, LinkedList<Integer> currentPath, boolean[] visited) {
        // 递归终止条件：路径长度等于数组长度，说明已经遍历完所有元素，可以加入结果集
        if (currentPath.size() == nums.length){
            result.add(new ArrayList<>(currentPath));
            return;
        }
        // 深度遍历每颗树的所有节点
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) { // 没有访问过则加入到路径中
                currentPath.push(nums[i]);
                visited[i] = true;
                dfs(nums, result, currentPath, visited);
                currentPath.pop(); // 回溯
                visited[i] = false; // 回溯
            }
        }
    }
}
